package main

// 77. 组合
// https://leetcode.cn/problems/combinations/
func combine(n int, k int) [][]int {
	ans := make([][]int, 0)
	var dfs func(pos int, path []int)
	dfs = func(pos int, path []int) {
		if len(path) == k {
			tmp := make([]int, k)
			copy(tmp, path)
			ans = append(ans, tmp)
			return
		}
		for i := pos; i <= n; i++ {
			path = append(path, i)
			dfs(i+1, path)
			path = path[:len(path)-1]
		}
	}
	dfs(1, []int{})
	return ans
}

// 216. 组合总和 III
// https://leetcode.cn/problems/combination-sum-iii/
func combinationSum3(k int, n int) [][]int {
	ans := make([][]int, 0)
	sum := 0
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if len(path) == k {
			if sum == n {
				tmp := make([]int, k)
				copy(tmp, path)
				ans = append(ans, tmp)
			}
			return
		}
		for i := pos; i <= 9; i++ {
			path = append(path, i)
			sum += i
			dfs(path, i+1)
			path = path[:len(path)-1]
			sum -= i
		}
	}
	dfs([]int{}, 1)
	return ans
}

// 17. 电话号码的字母组合
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	var mp map[string]string = map[string]string{
		"2": "abc",
		"3": "def",
		"4": "ghi",
		"5": "jkl",
		"6": "mno",
		"7": "pqrs",
		"8": "tuv",
		"9": "wxyz",
	}
	ans := make([]string, 0)
	var dfs func(path string, pos int)
	dfs = func(path string, pos int) {
		if pos == len(digits) {
			ans = append(ans, path)
			return
		}
		digit := mp[string(digits[pos])]
		for _, v := range digit {
			dfs(path+string(v), pos+1)
		}
	}
	dfs("", 0)
	return ans
}
